package leetcode_jz_offer.day22_weiyunsuan;

import java.util.HashMap;
import java.util.Map;

/**
 * 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。
 * 请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)
 **/
public class Num56_I数组中数字出现的次数 {
//    //map集合解决问题（开辟了新的空间）
//    Map<Integer,Integer> map=new HashMap<>();
//    public int[] singleNumbers(int[] nums) {
//        for (int i = 0; i < nums.length; i++) {
//            if(!map.containsKey(nums[i])){
//                map.put(nums[i],1);
//            }else {
//                map.put(nums[i],map.get(nums[i])+1 );
//            }
//        }
//        int[] res=new int[2];
//        int i=0;
//        for (Map.Entry<Integer,Integer> entry:map.entrySet()){
//            if(entry.getValue()==1){
//                res[i]=entry.getKey();
//                i++;
//            }
//        }
//        return res;
//    }
    //位运算解决问题
    /**
     * 分析：两个不一样的数a和b，其他数两两相等。考虑异或操作，相异为真，相同为假
     *      所以将数字全部异或，最后得到的结果一定是a^b。此时思考两者异或后结果x的二进制位
     *      xi=0时说明ab的位相同，异或后才能为0，xi=1说明ab对应位不同，相异或才为真
     *      两个数是不一样，所以a和b的对应位上至少有一个位ai,bi上的数字是不同的（如2和3，010，011，最低位数字不同）
     *      取不同的这个位（xi=1(aibi不同的位)的位），按这个位将数组分为两个数组，将a和b放在不同的数组中，如果该位为0就分到第一组，否则就分到第二组（xi=1则必然有一个是0一个是1，才能异或成xi=1）
     */
    /**
     * 算法
     * 先对所有数字进行一次异或，得到两个出现一次的数字的异或值。
     * 在异或结果中找到任意为1的位(找不为0的最低位即可)。
     * 根据这一位对所有的数字进行分组。
     * 在每个组内进行异或操作，得到两个数字。
     */
    public int[] singleNumbers(int[] nums) {
        int a=0;
        int b=0;
        int x=0;
        int div=1;//找两个数异或后结果的xi=1的位【1&1=1，1&0=0，当xi和div相与结果为1时xi一定为1】
        for (int num :nums) {
            x^=num;
        }
        //此时x=a^b,div循环左移直到xi=1
        while ((x&div)==0){
            div<<=1;
        }
        //此时找到了为1的位:...000div000...
        //按此位分组：该位异或结果是div=1，那么一定一个0一个1，是0一组，1另一组。让每个数与div相与，相与=0说明原该位是0，为1则原该位是1
        for (int num :nums) {
            if((num&div)==0){
                a^=num;//将组内数据异或
            }else {
                b^=num;
            }
        }
        return new int[]{a,b};
    }
}
